A “convex hull” is the set of points forming the smallest convex set that includes all of the points. Thus, the convex hull of two polygons is the smallest single convex polygon that encloses the two polygons. It is often useful in the field of computer science to obtain the convex hull of two polygons as quickly and efficiently as possible. For example, electronic ink may be rendered based upon a collection of sample points made with a stylus. If the electronic ink is intended to simulate the appearance of ink written with a chisel-tipped pen, then each of the sample points has a rectangular shape. Further, while the proportions of the rectangle for each sample point may be the same, the actual size of each rectangle may vary if the ink is created using a stylus and digitizer sensitive to pressure and angle differences in how the stylus is held. To accurately render the ink between two sample points, the sample points must be connected by lines that fully encompass the rectangle for each sample point. Thus, the rendered ink between two sample points is the convex hull encompassing the two rectangles making up the sample points.
As well as being useful for rendering electronic ink, a convex hull can also be used for other purposes in the field of computer science. For example, determining the convex hull of polygons is useful in rendering complex figures composed of convex polygons, such as in computer video games and other graphically-intensive applications. Similarly, a method for determining the convex hull of convex polygons can be used for tasks including collision detection between complex figures and determining whether one of the two polygons completely contains the other. In addition, there are a variety of other applications for techniques to determine the convex hull of two convex polygons.
While various techniques have been developed to calculate the convex hull of two polygons, these techniques are laborious and require a number of operations on the order of O(N1nN), where N is the number of vertices in each polygon. To render ink smoothly and in synchronism with the movement of the stylus, however, the ink must be generated and rendered very quickly. Accordingly, various aspects of the invention are directed to techniques for determining the convex hull of two polygons having congruent corresponding angles more quickly and efficiently than conventional techniques. Advantageously, various examples of the invention allow the convex hull to be determined using a number of operations on the order of O(N), rather than O(N1nN) as with conventional techniques.